package 递归练习;

import java.util.Arrays;

public class test1 {
   public static int f1(int n){//阶乘问题
       if(n==1){
           return 1;
       }
       return n*f1(n-1);
   }
   public static  void f2(int n,String str){
       if(n==str.length()){
           return;
       }
       f2(n+1,str);
           System.out.println(str.charAt(n));
   }
   public static int f3(int []a,int target,int i,int j) {
       if (i > j) {
           return -1;
       }
       int m = (i + j) >>> 1;//求取中间值
       if (target < a[m]) {
           return f3(a, target, i, m -1);
       } else if (target > a[m]) {
           return f3(a, target, m +1, j);
       } else {
           return m;
       }
   }
   public static void loop(int a[]){//利用static可以直接调用方法，无需利用对象
       for (int i = 0; i <a.length ; i++) {
           System.out.println(a[i]);
       }
   }
   public static void bubble(int []a,int j){
       if(j==0){
           return;
       }
       for (int i = 0; i <j ; i++) {//依次把最后一个改成最大值
           if(a[i]>a[i+1]){
               int t=a[i];
               a[i]=a[i+1];
               a[i+1]=t;
           }
       }
       bubble(a,j-1);
   }
   public static void bubble2(int []a,int j){
       if(j==0){
           return;
       }
       int x=0;
       for (int i = 0; i < j; i++) {
           int t=a[i];
           a[i]=a[i+1];
           a[i+i]=t;
           x=i;//交换到无需交换的最大值，减少递归次数
       }
       bubble2(a,x);
   }
   public static void insertian(int []a,int low){
       if(low==a.length){
           return;
       }
       int t=a[low];
       int i=low-1;//已排序的位置
       while(i>=0&&a[i]>t){//把要排序的值抽取出来，找到合适的，安插
           a[i+1]=a[i];
           i--;
       }
       a[i+1]=t;
       insertian(a,low+1);
   }

   public static int f4(int n){//斐波那契数列
       if(n==0){
           return 0;
       }
       if(n==1){
           return 1;
       }
       int x=f4(n-1);
       int y=f4(n-2);
       return x+y;
   }
   public static int fibonacci(int n){
       int []cache=new int [n+1];
       Arrays.fill(cache,-1);//初始值改为-1
       cache[0]=0;
       cache[1]=1;
       return f5(n,cache);
   }
   public static int f5(int n,int[] cache){
       if(cache[n]!=-1){
           return cache[n];
       }
       int x=f5(n-1,cache);
       int y=f5(n-2,cache);
       return cache[n];
   }


    public static void main(String[] args) {
       /* int a=f1(4);
        System.out.println(a);
        f2(0,"abcd");*/
        int b[]={1,2,3,4,5,7,8,9,10};
        int c[]={3,2,5,3,6,7};
        /*System.out.println(f3(b,2,0,4));*/
        bubble(c,5);
        loop(c);
        System.out.println(f4(10));
    }
}
